//题目:
// 给你一个整数数组nums和一个整数k,请你返回其中出现频率前k高的元素。
// 你可以按任意顺序返回答案。
#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;
//代码:
class Solution 
{
    struct compare
    {
        bool operator()(const pair<int,int> pir1,const pair<int,int> pir2)
        {
            return pir1.second>pir2.second;//建小根堆，排升序
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        //1.用一个哈希表统计nums每个元素出现的次数
        unordered_map<int,int> hash;
        for(const auto& x:nums)hash[x]++;
        //2.对second建小根堆，排升序
        priority_queue<pair<int,int>,vector<pair<int,int>>,compare> heap;//key是元素值，value是元素个数
        //3.插入元素
        for(const auto& pir:hash)
        {
            heap.push(pir);
            if(heap.size()>k)heap.pop();//出现次数少的元素丢掉，保留出现次数高的元素
        }
        //4.提取结果
        vector<int> ret;
        while(!heap.empty())
        {
            ret.push_back(heap.top().first);
            heap.pop();
        }
        return ret;
    }
};